package com.wwz.leetcode;

import com.wwz.common.ListNode;
import org.junit.Test;

public class LeetCode92 {


    @Test
    public void test() {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        //ListNode head = new ListNode(5, null);
        //ListNode head = new ListNode(3, new ListNode(5));
        reverseBetween(head, 1, 5);

    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode leftNode = null, pre = null;
        leftNode = head;
        for (int i = 1; i < left; i++) {
            pre = leftNode;
            leftNode = leftNode.next;
        }
        // 避免重复遍历
        ListNode rightNode = leftNode;
        for (int i = 1; i <= right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        //反转链表
        ListNode reverse = reverse(leftNode, rightNode);

        if (pre != null) {
            // 前指针拼接反转部分
            pre.next = reverse;
            // 最后一个节点和剩余部分相连接
            leftNode.next = rightNode;
            return head;
        } else {
            leftNode.next = rightNode;
            return reverse;
        }
    }

    public ListNode reverse(ListNode leftNode, ListNode rightNode) {
        ListNode pre = null, next = null;
        while (leftNode != rightNode) {
            next = leftNode.next;
            //头插
            leftNode.next = pre;
            // leftNode 变成了 pre
            pre = leftNode;
            leftNode = next;
        }
        return pre;
    }
}
